package 队列;

import com.alibaba.fastjson.JSON;
import javafx.util.Pair;
import 栈.TreeNode;

import java.util.*;

public class No102二叉树的层序遍历 {

    /**
     * 给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
     *
     * 示例：
     * 二叉树：[3,9,20,null,null,15,7],
     *     3
     *    / \
     *   9  20
     *     /  \
     *    15   7
     * 返回其层次遍历结果：
     * [
     *   [3],
     *   [9,20],
     *   [15,7]
     * ]
     */

    /**
     * 最优解法:先加进去,然后两个while即可
     */
    public static List<List<Integer>> levelOrderGood(TreeNode root) {

        if(root==null)
            return new ArrayList<>();
        List<List<Integer>> lists=new ArrayList<>();
        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()){
            //先吃进一个节点
            int count=queue.size();
            List<Integer> list=new ArrayList<>();
            while (count>0){
                /**
                 * 这里会遍历完这一层的节点,然后顺便它们的子节点吃入
                 */
                TreeNode poll = queue.poll();
                if(poll.left!=null)//有count加持,此处不会错
                    queue.add(poll.left);
                if(poll.right!=null)
                    queue.add(poll.right);
                list.add(poll.val);
                count--;
            }
            lists.add(list);
        }
        return lists;
    }

    public static void main(String[] args) {
        TreeNode node = TreeNode.getNode();
        System.out.println(JSON.toJSONString(levelOrderGood(node)));
    }

}
